This Application is related to the following Application:
Warping Geometric Objects, by Hongche Liu and Shyam Kuttikkad, filed the same day as the present application.
The above-cited Application is incorporated herein by reference.
1. Field of Invention
The present invention is directed toward analyzing sets of geometric objects.
2. Description of Related Art
Physical areas are often modeled using geometric objects. Examples of such physical areas include a geographic region and a building""s floor plan. One example of a model using two-dimensional geometric objects is a map of a geographic region, such as a city.
FIG. 1 illustrates a map that is formed by a set of geometric objects. The objects in FIG. 1 include points 60-70, arcs 80-91, and polygons 50-51. Each arc 80-91 represents a road and is bounded at each of its ends by a point. For example, arc 80 is bounded at one end by point 60 and at another end by point 62. Each arc can be co-bounded by one or two polygons. For example, arc 86 is co-bounded by polygons 50 and 51, while arc 85 is only co-bounded by polygon 50. Each polygon 50 and 51 is formed by a set of arcs that define the boundary of the polygon. For example, polygon 50 is defined by boundary arcs 81, 82, 83, 84, 85, and 86.
Different models of the same physical area often provide different quality details about the area. Differences between models of the same area can occur, because models can be distorted, so that all the features in the model are not depicted in their true positions. Such distortions are often localized, with different regions of the model being distorted differently. In paper models, distortion can be caused by paper stretching, folding, and scaling. In electronic models, distortion can be caused when the model is transformed into digital form.
By repositioning different models of the same area, a more accurate new model can be created. FIG. 2 illustrates a map 100 of an area that is neither very smooth nor accurate. FIG. 3 shows a more accurate map 110 of the same area as map 100. The differences between maps 100 and 110 are illustrated in FIG. 4, which shows an overlay 120 of maps 100 and 110. A repositioning process can be performed to utilize the details of both maps 100 and 110 to obtain an improved new map.
The use of repositioning is particularly beneficial and practical in generating electronic maps. There are often many different maps available for a particular region. By making use of a computer to reposition the many maps that are available for a region, a very accurate new map can be generated in a time efficient and cost efficient manner.
When performing repositioning, matching points in the models being repositioned are identified and employed to generate a transformation model for warping points in one of the models into a new model. In order to determine matching points, matching arcs in the models are first identified and then used in a process for identifying the matching points.
Traditional processes for identifying matching arcs typically use attributes associated with the arcs to identify matches. For maps, one example of such as attribute is a street name that is associated with an arc. In such an example, matching arcs can be identified by finding arcs with matching street names. However, many models do not provide attributes for each arc. As a result, less matching arcs and matching points are identified, thereby compromising the repositioning result.
Accordingly, there is a need for identifying matching arcs in a set of models without relying on attributes being associated with the arcs.
The present invention, roughly described, provides for identifying matching arcs in sets of geometric objects, such as a pair of electronic maps, without relying on attributes being assigned to the arcs. Matching arcs are identified by making use of the geometric and topological information that is associated with each set of geometric objects.
An arc in a first set of geometric objects is identified as matching an arc in a second set of geometric objects, when the arc in the first set is co-bounded on both sides by polygons which match the corresponding co-bounding polygons of the arc in the second set. Accordingly, an initial determination is made of which polygons in the first set of geometric objects match polygons in the second set of geometric objects.
Polygon matching is performed by determining a set of similarity metrics for each pairing of a polygon in the first set of geometric objects and a polygon in the second set of geometric objects. The polygons with the greatest degree of similarity, based on the set of similarity metrics, are then identified as matching, provided a minimum degree of similarity is indicated by the set of similarity metrics. In accordance with the present invention, similarity metrics for proximity, area, shape and rotation are determined. Further, each of these metrics are determined in an isolated fashion, so that no other metric is reflected in the metric being measured.
Once matching arcs are identified, they are assigned attributes. In one embodiment of the present invention, the assigned attribute is a label formed by a concatenation of assigned unique identifiers for each co-bounding matched polygon. In an alternate embodiment, the assigned attribute is a label, such as a street name. The assigned attributes enable traditional attribute-based arc matching followed by node matching to utilize the identified arcs for locating matching points in the first set of geometric objects and the second set of geometric objects.
These and other objects and advantages of the present invention will appear more clearly from the following description in which the preferred embodiment of the present invention has been set forth in conjunction with the drawings.